//最后一块石头的重量
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq(stones.begin(),stones.end());
        while(pq.size() > 1)
        {
            int x = pq.top();
            pq.pop();
            int y = pq.top();
            pq.pop();
            if(y < x) swap(x,y);
            int z = y-x;
            if(z) pq.push(z);
        }
        if(pq.empty()) return 0;
        else return pq.top();
    }
};

//数据流中的第k大元素
class KthLargest {
public:
    KthLargest(int k, vector<int>& nums):_k(k)
    {
        for(auto& e : nums)
        {
            _pq.push(e);
            if(_pq.size() > k) _pq.pop();
        }
    }
    
    int add(int val) {
        _pq.push(val);
        if(_pq.size() > _k) _pq.pop();
        return _pq.top();
    }
    priority_queue<int,vector<int>,greater<int>> _pq;
    int _k;
};
//前k个高频单词
class Solution {
public:
    struct Compare
    {
        bool operator()(pair<string,int> p1,pair<string,int> p2)
        {
            if(p1.second == p2.second)
            {
                return p1.first > p2.first;
            }
            else 
            {
                return p1.second < p2.second;
            }
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> hash;
        for(auto word : words)
        {
            hash[word]++;
        }
        priority_queue<pair<string,int>,vector<pair<string,int>>,Compare> pq(hash.begin(),hash.end());
        vector<string> ret; 
        for(size_t i = 0 ; i < k ; ++i)
        {
            auto top = pq.top();
            pq.pop();
            ret.push_back(top.first);
        }
        return ret;
    }
};
//数据流的中位数
class MedianFinder {
public:
    MedianFinder() {
    }
    
    void addNum(int num) {
        //判断这个num该进哪
        int m = BigHeap.size();
        int n = SmallHeap.size();
        //性质：m==n || m+1==n
        if(m == n)
        {
            if(BigHeap.empty())
            {
                BigHeap.push(num);
                return;
            }
            //判断num的值
            if(num <= BigHeap.top())
            {
                //直接进
                BigHeap.push(num);
            }
            else 
            {
                //进右边堆
                SmallHeap.push(num);
                //维护性质
                BigHeap.push(SmallHeap.top());
                SmallHeap.pop();
            }
        }
        else
        {
            //大堆比小堆多一个
            if(num <= BigHeap.top())
            {
                //直接进
                BigHeap.push(num);
                //大堆比小堆多两个，维护性质
                SmallHeap.push(BigHeap.top());
                BigHeap.pop();
            }
            else
            {
                //进小堆，不需要维护性质
                SmallHeap.push(num);
            }
        }
    }
    
    double findMedian() {
        if(BigHeap.size() == SmallHeap.size())
        {
            double val1 = BigHeap.top();
            double val2 = SmallHeap.top();
            return (val1+val2)/2;
        }
        else 
        {
            return BigHeap.top();
        }
    }
    priority_queue<int> BigHeap;//left
    priority_queue<int,vector<int>,greater<int>> SmallHeap;//right;
};